#include <stdio.h>
#include <strings.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#include "shape.h"
#include "flp.h"
#include "util.h"

/* make a shape curve from area and aspect ratios	*/
shape_t *shape_from_aspect(double area, double min,
                           double max, int32_t rotable,
                           int32_t n_orients)
{
    shape_t *shape;
    double r=1, minx, maxx, tmin, tmax;
    int32_t i, overlap = 0;

    /* rotatable blocks have 2n no. of orients	*/
    if (n_orients <= 1 || (n_orients & 1))
        fatal("n_orients should be an even number greater than 1\n");

    shape = (shape_t *) calloc(1, sizeof(shape_t));
    if (!shape)
        fatal("memory allocation error\n");
    if (min == max)
        shape->size = 1 + (!!rotable);
    else
        shape->size = n_orients;

    shape->x = (double *) calloc(shape->size, sizeof(double));
    shape->y = (double *) calloc(shape->size, sizeof(double));
    if (!shape->x || !shape->y)
        fatal("memory allocation error\n");

    /* overlapping regions of aspect ratios */
    if (rotable && min <= 1.0 && max >= 1.0) {
        overlap = 1;
        tmin = MIN4(min, max, 1.0/min, 1.0/max);
        tmax = MAX4(min, max, 1.0/min, 1.0/max);
        min = tmin;
        max = tmax;
    }

    if (!rotable || overlap) {
        minx = sqrt(area * min);
        maxx = sqrt(area * max);
        if (shape->size > 1)
            r = pow((maxx / minx) , 1.0/(shape->size-1));
        for (i = 0; i < shape->size; i++) {
            shape->x[i] = minx * pow(r, i);
            shape->y[i] = area / shape->x[i];
        }
        /* rotable but no overlap, hence two sets of orientations	*/
    } else {
        int32_t n = shape->size / 2;
        /* orientations with aspect ratios < 1	*/
        tmin = MIN(min, 1.0/min);
        tmax = MIN(max, 1.0/max);
        minx = sqrt(area * MIN(tmin, tmax));
        maxx = sqrt(area * MAX(tmin, tmax));
        if ( n > 1)
            r = pow((maxx / minx) , 1.0/(n-1));
        for (i = 0; i < n; i++) {
            shape->x[i] = minx * pow(r, i);
            shape->y[i] = area / shape->x[i];
        }
        /* orientations with aspect ratios > 1	*/
        tmin = MAX(min, 1.0/min);
        tmax = MAX(max, 1.0/max);
        minx = sqrt(area * MIN(tmin, tmax));
        maxx = sqrt(area * MAX(tmin, tmax));
        if ( n > 1)
            r = pow((maxx / minx) , 1.0/(n-1));
        for (i = 0; i < n; i++) {
            shape->x[n+i] = minx * pow(r, i);
            shape->y[n+i] = area / shape->x[n+i];
        }
    }
    return shape;
}

void free_shape(shape_t *shape)
{
    free (shape->x);
    free (shape->y);
    if(shape->left_pos) {
        free(shape->left_pos);
        free(shape->right_pos);
        free(shape->median);
    }
    free(shape);
}

void print_shape_entry(shape_t *shape, int32_t i)
{
    fprintf(stdout, "%.5f\t%.5f", shape->x[i], shape->y[i]);
    if (shape->left_pos)
        fprintf(stdout, "\t%d\t%d\t%.5f", shape->left_pos[i],
                shape->right_pos[i], shape->median[i]);
    fprintf(stdout, "\n");
}

/* debug print  */
void print_shape(shape_t *shape)
{
    int32_t i;
    if (!shape) {
        fprintf(stdout, "printing shape curve: NULL\n");
        return;
    }
    fprintf(stdout, "printing shape curve with %d elements\n", shape->size);
    for (i=0; i < shape->size; i++)
        print_shape_entry(shape, i);
    fprintf(stdout, "\n");
}

/* shape curve arithmetic	*/
shape_t *shape_add(shape_t *shape1, shape_t *shape2, int32_t cut_type)
{
    int32_t i=0, j=0, k=0, total=0, m, n;
    shape_t *sum;

    sum = (shape_t *) calloc(1, sizeof(shape_t));
    if (!sum)
        fatal("memory allocation error\n");

    /* shortcuts	*/
    m = shape1->size;
    n = shape2->size;

    /* determine result size	*/
    while(i < m && j < n) {
        if (cut_type == CUT_VERTICAL) {
            if (shape1->y[i] >= shape2->y[j])
                i++;
            else
                j++;
        } else {
            if (shape1->x[m-1-i] >= shape2->x[n-1-j])
                i++;
            else
                j++;
        }
        total++;
    }

    sum->x = (double *) calloc(total, sizeof(double));
    sum->y = (double *) calloc(total, sizeof(double));
    sum->left_pos = (int32_t *) calloc(total, sizeof(int));
    sum->right_pos = (int32_t *) calloc(total, sizeof(int));
    sum->median = (double *) calloc(total, sizeof(double));
    if (!sum->x || !sum->y || !sum->left_pos ||
            !sum->right_pos || !sum->median)
        fatal("memory allocation error\n");
    sum->size = total;

    i=j=0;
    while(i < m && j < n) {
        /* vertical add	*/
        if (cut_type == CUT_VERTICAL) {
            sum->x[k] = shape1->x[i] + shape2->x[j];
            sum->y[k] = MAX(shape1->y[i], shape2->y[j]);
            sum->left_pos[k] = i;
            sum->right_pos[k] = j;
            sum->median[k] = shape1->x[i];
            if (shape1->y[i] >= shape2->y[j])
                i++;
            else
                j++;
            /* horizontal add */
        } else {
            /*
             * direction of increasing 'y' is the reverse of the
             * regular direction of the shape curve. hence reverse
             * the curve before adding
             */
            sum->x[total-1-k] = MAX(shape1->x[m-1-i], shape2->x[n-1-j]);
            sum->y[total-1-k] =  shape1->y[m-1-i] + shape2->y[n-1-j];
            sum->left_pos[total-1-k] = m-1-i;
            sum->right_pos[total-1-k] = n-1-j;
            sum->median[total-1-k] = shape1->y[m-1-i];
            if (shape1->x[m-1-i] >= shape2->x[n-1-j])
                i++;
            else
                j++;
        }
        k++;
    }

    return sum;
}

/* copy a shape curve	*/
shape_t *shape_duplicate(shape_t *shape)
{
    shape_t *copy;
    int32_t i;
    copy = (shape_t *) calloc(1, sizeof(shape_t));
    if (!copy)
        fatal("memory allocation error\n");
    copy->size = shape->size;
    copy->x = (double *) calloc(copy->size, sizeof(double));
    copy->y = (double *) calloc(copy->size, sizeof(double));
    if (!copy->x || !copy->y)
        fatal("memory allocation error\n");
    if (shape->left_pos) {
        copy->left_pos = (int32_t *) calloc(copy->size, sizeof(int));
        copy->right_pos = (int32_t *) calloc(copy->size, sizeof(int));
        copy->median = (double *) calloc(copy->size, sizeof(double));
        if(!copy->left_pos || !copy->right_pos || !copy->median)
            fatal("memory allocation error\n");
    }
    for(i=0; i < shape->size; i++) {
        copy->x[i] = shape->x[i];
        copy->y[i] = shape->y[i];
        if (shape->left_pos) {
            copy->left_pos[i] = shape->left_pos[i];
            copy->right_pos[i] = shape->right_pos[i];
            copy->median[i] = shape->median[i];
        }
    }
    return copy;
}

/* tree node stack operations	*/

/* constructor	*/
tree_node_stack_t *new_tree_node_stack(void)
{
    tree_node_stack_t *stack;
    stack = (tree_node_stack_t *)calloc(1, sizeof(tree_node_stack_t));
    if (!stack)
        fatal("memory allocation error\n");
    /* first free location	*/
    stack->top = 0;
    return stack;
}

/* destructor	*/
void free_tree_node_stack(tree_node_stack_t *stack)
{
    free(stack);
}

/* is empty?	*/
int32_t tree_node_stack_isempty(tree_node_stack_t *stack)
{
    if (stack->top <= 0)
        return TRUE;
    return FALSE;
}

/* is full?	*/
int32_t tree_node_stack_isfull(tree_node_stack_t *stack)
{
    if (stack->top >= MAX_STACK)
        return TRUE;
    return FALSE;
}

/* push	*/
void tree_node_stack_push(tree_node_stack_t *stack, tree_node_t *node)
{
    if (!tree_node_stack_isfull(stack)) {
        stack->array[stack->top] = node;
        stack->top++;
    } else
        fatal("attempting to push into an already full stack\n");
}

/* pop	*/
tree_node_t *tree_node_stack_pop(tree_node_stack_t *stack)
{
    if (!tree_node_stack_isempty(stack)) {
        stack->top--;
        return stack->array[stack->top];
    } else {
        fatal("attempting to pop from an already empty stack\n");
        return NULL;
    }
}

/* clear	*/
void tree_node_stack_clear(tree_node_stack_t *stack)
{
    stack->top = 0;
}

/* slicing tree routines	*/

/* construct floorplan slicing tree from NPE	*/
tree_node_t *tree_from_NPE(flp_desc_t *flp_desc,
                           tree_node_stack_t *stack,
                           NPE_t *expr)
{
    int32_t i;
    tree_node_t *node = NULL, *left, *right;

    if (!tree_node_stack_isempty(stack))
        fatal("stack not empty\n");

    for (i=0; i < expr->size; i++) {
        node = (tree_node_t *) calloc(1, sizeof(tree_node_t));
        if (!node)
            fatal("memory allocation error\n");
        /* leaf */
        if (expr->elements[i] >= 0) {
            node->curve = shape_duplicate(flp_desc->units[expr->elements[i]].shape);
            node->left = node->right = NULL;
            node->label.unit = expr->elements[i];
            /*	internal node denoting a cut	*/
        } else {
            right = tree_node_stack_pop(stack);
            left = tree_node_stack_pop(stack);
            node->curve = shape_add(left->curve, right->curve, expr->elements[i]);
            node->left = left;
            node->right = right;
            node->label.cut_type = expr->elements[i];
        }
        tree_node_stack_push(stack, node);
    }

    tree_node_stack_clear(stack);
    return node;
}

void free_tree(tree_node_t *root)
{
    if (root->left != NULL)
        free_tree(root->left);
    if (root->right != NULL)
        free_tree(root->right);
    free_shape(root->curve);
    free(root);
}

/* debug print	*/
void print_tree(tree_node_t *root, flp_desc_t *flp_desc)
{
    if(root->left != NULL)
        print_tree(root->left, flp_desc);
    if (root->right != NULL)
        print_tree(root->right, flp_desc);

    if (root->label.unit >= 0)
        fprintf(stdout, "printing shape curve for %s\n", flp_desc->units[root->label.unit].name);
    else if (root->label.cut_type == CUT_VERTICAL)
        fprintf(stdout, "printing shape curve for VERTICAL CUT\n");
    else if (root->label.cut_type == CUT_HORIZONTAL)
        fprintf(stdout, "printing shape curve for HORIZONTAL CUT\n");
    else
        fprintf(stdout, "unknown cut type\n");

    print_shape(root->curve);
}

/*
 * print only the portion of the shape curves
 * corresponding to the `pos'th entry of root->curve
 */
void print_tree_relevant(tree_node_t *root, int32_t pos, flp_desc_t *flp_desc)
{
    if(root->left != NULL)
        print_tree_relevant(root->left, root->curve->left_pos[pos], flp_desc);
    if (root->right != NULL)
        print_tree_relevant(root->right, root->curve->right_pos[pos], flp_desc);

    if (root->label.unit >= 0)
        fprintf(stdout, "printing orientation for %s:\t", flp_desc->units[root->label.unit].name);
    else if (root->label.cut_type == CUT_VERTICAL)
        fprintf(stdout, "printing orientation for VERTICAL CUT:\t");
    else if (root->label.cut_type == CUT_HORIZONTAL)
        fprintf(stdout, "printing orientation for HORIZONTAL CUT:\t");
    else
        fprintf(stdout, "unknown cut type\n");

    print_shape_entry(root->curve, pos);
}

int32_t min_area_pos(shape_t *curve)
{
    int32_t i = 1, pos = 0;
    double min = curve->x[0] * curve->y[0];
    for (; i < curve->size; i++)
        if (min > curve->x[i] * curve->y[i]) {
            min = curve->x[i] * curve->y[i];
            pos = i;
        }
    return pos;
}

/*
 * recursive sizing - given the slicing tree containing
 * the added up shape curves. 'pos' denotes the current
 * added up orientation. 'leftx' & 'bottomy' denote the
 * left and bottom ends of the current bounding rectangle
 */
int32_t recursive_sizing (tree_node_t *node, int32_t pos,
                          double leftx, double bottomy,
                          int32_t dead_count, int32_t compact_dead,
                          double compact_ratio,
#if VERBOSE > 1
                          double *compacted_area,
#endif
                          flp_t *flp)
{
    /* shortcut	*/
    shape_t *self = node->curve;

    /* leaf node. fill the placeholder	*/
    if (node->label.unit >= 0) {
        flp->units[node->label.unit].width = self->x[pos];
        flp->units[node->label.unit].height = self->y[pos];
        flp->units[node->label.unit].leftx = leftx;
        flp->units[node->label.unit].bottomy = bottomy;
    } else {
        /* shortcuts */
        int32_t idx;
        double x1, x2, y1, y2;
        shape_t *left = node->left->curve;
        shape_t *right = node->right->curve;

        /* location of the first dead block	+ offset */
        idx = (flp->n_units + 1) / 2 + dead_count;

        x1 = left->x[self->left_pos[pos]];
        x2 = right->x[self->right_pos[pos]];
        y1 = left->y[self->left_pos[pos]];
        y2 = right->y[self->right_pos[pos]];

        /* add a dead block - possibly of zero area	*/
        if (node->label.unit == CUT_VERTICAL) {
            /*
             * if a dead block has been previously compacted away from this
             * bounding rectangle, absorb that area into the child also
             */
            if(self->y[pos] > MAX(y1, y2)) {
                y1 = left->y[self->left_pos[pos]] += (self->y[pos] - MAX(y1, y2));
                y2 = right->y[self->right_pos[pos]] += (self->y[pos] - MAX(y1, y2));
            }
            if(self->x[pos] > (x1+x2))
                x2 = right->x[self->right_pos[pos]] += self->x[pos]-(x1+x2);

            flp->units[idx].width = (y2 >= y1) ? x1 : x2;
            flp->units[idx].height = fabs(y2 - y1);
            flp->units[idx].leftx = leftx + ((y2 >= y1) ? 0 : x1);
            flp->units[idx].bottomy = bottomy + MIN(y1, y2);

            /*
             * ignore dead blocks smaller than compact_ratio times the area
             * of the smaller of the constituent rectangles. instead, increase
             * the size of the rectangle by that amount
             */
            if (compact_dead && fabs(y2-y1) / MIN(y1, y2) <= compact_ratio) {
#if VERBOSE > 1
                *compacted_area += (flp->units[idx].width * flp->units[idx].height);
#endif
                if (y2 >= y1)
                    left->y[self->left_pos[pos]] = y2;
                else
                    right->y[self->right_pos[pos]] = y1;
            } else {
                dead_count++;
            }

            /* left and bottom don't change for the left child	*/
            dead_count = recursive_sizing(node->left, self->left_pos[pos],
                                          leftx, bottomy, dead_count, compact_dead,
                                          compact_ratio,
#if VERBOSE > 1
                                          compacted_area,
#endif
                                          flp);
            dead_count = recursive_sizing(node->right, self->right_pos[pos],
                                          leftx + self->median[pos], bottomy,
                                          dead_count, compact_dead, compact_ratio,
#if VERBOSE > 1
                                          compacted_area,
#endif
                                          flp);
        } else {
            if(self->x[pos] > MAX(x1, x2)) {
                x1 = left->x[self->left_pos[pos]] += (self->x[pos] - MAX(x1, x2));
                x2 = right->x[self->right_pos[pos]] += (self->x[pos] - MAX(x1, x2));
            }
            if(self->y[pos] > (y1+y2))
                y2 = right->y[self->right_pos[pos]] += self->y[pos]-(y1+y2);

            flp->units[idx].width = fabs(x2 - x1);
            flp->units[idx].height = (x2 >= x1) ? y1 : y2;
            flp->units[idx].leftx = leftx + MIN(x1, x2);
            flp->units[idx].bottomy = bottomy + ((x2 >= x1) ? 0 : y1);

            if (compact_dead && fabs(x2-x1) / MIN(x1, x2) <= compact_ratio) {
#if VERBOSE > 1
                *compacted_area += (flp->units[idx].width * flp->units[idx].height);
#endif
                if (x2 >= x1)
                    left->x[self->left_pos[pos]] = x2;
                else
                    right->x[self->right_pos[pos]] = x1;
            } else {
                dead_count++;
            }

            /* left and bottom don't change for the left child	*/
            dead_count = recursive_sizing(node->left, self->left_pos[pos],
                                          leftx, bottomy, dead_count, compact_dead,
                                          compact_ratio,
#if VERBOSE > 1
                                          compacted_area,
#endif
                                          flp);
            dead_count = recursive_sizing(node->right, self->right_pos[pos],
                                          leftx, bottomy + self->median[pos],
                                          dead_count, compact_dead, compact_ratio,
#if VERBOSE > 1
                                          compacted_area,
#endif
                                          flp);
        }
    }
    return dead_count;
}

/*
 * convert slicing tree into actual floorplan
 * returns the number of dead blocks compacted
 */
int32_t tree_to_flp(tree_node_t *root, flp_t *flp, int32_t compact_dead,
                    double compact_ratio)
{
    /* for now, only choose the floorplan with
     * the minimum area regardless of the overall
     * aspect ratio
     */
    int32_t pos = min_area_pos(root->curve);
#if VERBOSE > 1
    double compacted_area = 0.0;
#endif
    int32_t dead_count = recursive_sizing(root, pos, 0.0, 0.0, 0,
                                          compact_dead, compact_ratio,
#if VERBOSE > 1
                                          &compacted_area,
#endif
                                          flp);

    int32_t compacted = (flp->n_units - 1) / 2 - dead_count;
    flp->n_units -= compacted;
#if VERBOSE > 1
    fprintf(stdout, "%d dead blocks, %.2f%% of the core compacted\n", compacted,
            compacted_area / (get_total_area(flp)-compacted_area) * 100);
#endif
    return compacted;
}
